package com.wx.algorithm.sort;

import com.wx.ArrayUtils;

/**
 * @ClassName SimpleFastSort
 * @Author wx
 * @Description 代码简化版快排
 * 随机快排-时间复杂度O(n*long(n))
 * 经典快排-时间复杂度O(n2)
 * 空间复杂度O(long(n))
 * @Date 2020-03-28-21:05
 */
public class SimpleFastSort {


    /**
     * 排序实现
     */
    public static void sort(int[] array) {
        if (ArrayUtils.arrayValidation(array)) {
            return;
        }
        sortRun(array, 0, array.length - 1);
    }

    public static void sortRun(int[] array, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            //随机交换最后下标
            int newEnd = startIndex + (int) (Math.random() * (endIndex - startIndex + 1));
            ArrayUtils.swop(array, newEnd, endIndex);

            int[] partition = partition(array, startIndex, endIndex);
            sortRun(array, startIndex, partition[0]);
            sortRun(array, partition[1] + 1, endIndex);
        }
    }

    /**
     * 1.左边当前下标<右边界，左边当前下标与++左边界交换，左边当前下标++
     * 2.左边当前下标=右边界，左边当前下标++
     * 3.左边当前下标>右边界，左边当前下标与--右边当前下标位置交换
     * 4.左边当前下标=右边当前下标，右边界与右边界当前下标交换
     */
    public static int[] partition(int[] array, int startIndex, int endIndex) {
        //定义左右边界
        int l = startIndex - 1;
        int r = endIndex;

        while (startIndex < endIndex) {
            if (array[startIndex] < array[r]) {
                ArrayUtils.swop(array, startIndex, ++l);
                startIndex++;
            } else if (array[startIndex] > array[r]) {
                ArrayUtils.swop(array, startIndex, --endIndex);
            } else {
                startIndex++;
            }
        }


        ArrayUtils.swop(array, r, endIndex);

        //返回相等区域边界开始与结束位置
        return new int[]{l, endIndex};
    }

    public static void main(String[] agrs) {
        ArrayUtils.logarithmicRun(10000, 100, 20, SimpleFastSort::sort);
    }
}
